package likou;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/01/11 03:42
 */
public class _1202 {
    public static void main(String[] args) {
        List<List<Integer>> pairs = new ArrayList<>();
        pairs.add(new ArrayList<Integer>(Arrays.asList(2, 4)));
        pairs.add(new ArrayList<Integer>(Arrays.asList(5, 7)));
        pairs.add(new ArrayList<Integer>(Arrays.asList(1, 0)));
        pairs.add(new ArrayList<Integer>(Arrays.asList(0, 0)));
        pairs.add(new ArrayList<Integer>(Arrays.asList(4, 7)));
        pairs.add(new ArrayList<Integer>(Arrays.asList(0, 3)));
        pairs.add(new ArrayList<Integer>(Arrays.asList(4, 1)));
        pairs.add(new ArrayList<Integer>(Arrays.asList(1, 3)));
        System.out.println(smallestStringWithSwaps("fqtvkfkt", pairs));
    }

    public static String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        pairs.sort(Comparator.comparingInt(l -> l.get(0)));
        List<int[][]> list = new ArrayList<>();//可能有多组需要排序的下标
        char[] sb = s.toCharArray();
        sort(sb, pairs, list);
        //list.get(i)[1][1]~list.get(i)[1][list.get(i)[0]]是需要排序的部分
        for (int[][] now : list) {
            int[] nowIs = new int[now[1][0]];
            System.arraycopy(now[1], 1, nowIs, 0, nowIs.length);
            Arrays.sort(nowIs);
            quickSort(sb, nowIs, 0, nowIs.length - 1);
        }
        return new String(sb);
    }

    //取出需要排序的部分
    //poi[0]存的是当前已存在的位置，置为1，比如0在数组中，则poi[0][0]=1
    //poi[1]存的是需要排序的下标：poi[1][0]存的是排序下标个数
    //List<int[][]> list = new ArrayList<>();//可能有多组需要排序的下标
    private static void sort(char[] sb, List<List<Integer>> pairs, List<int[][]> list) {
        for (List<Integer> nowL : pairs) {
            boolean p = false;//该nowL是否存入目标list
            for (int[][] now : list) {
                if (now[0][nowL.get(0)] == 1 && now[0][nowL.get(1)] == 1) {
                    p = true;
                    break;
                }
                if (now[0][nowL.get(0)] == 1) {
                    now[0][nowL.get(1)] = 1;
                    now[1][++now[1][0]] = nowL.get(1);
                    p = true;
                    break;
                }
                if (now[0][nowL.get(1)] == 1) {
                    now[0][nowL.get(0)] = 1;
                    now[1][++now[1][0]] = nowL.get(0);
                    p = true;
                    break;
                }
            }
            if (!p) {
                int[][] poi = new int[2][sb.length + 1];
                poi[0][nowL.get(0)] = 1;
                poi[1][++poi[1][0]] = nowL.get(0);
                if (!nowL.get(0).equals(nowL.get(1))) {
                    poi[0][nowL.get(1)] = 1;
                    poi[1][++poi[1][0]] = nowL.get(1);
                }
                list.add(poi);
            }
        }
    }

    public static void quickSort(char[] arr, int[] nowIs, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int prvotIndex = partition(arr, nowIs, startIndex, endIndex);

        quickSort(arr, nowIs, startIndex, prvotIndex - 1);
        quickSort(arr, nowIs, prvotIndex + 1, endIndex);
    }

    private static int partition(char[] arr, int[] nowIs, int startIndex, int endIndex) {
        char pivot = arr[nowIs[startIndex]];
        int left = startIndex;
        int right = endIndex;
        while (left != right) {
            while (left < right && arr[nowIs[right]] > pivot) {
                right--;
            }
            while (left < right && arr[nowIs[left]] <= pivot) {
                left++;
            }
            if (left < right) {
                char p = arr[nowIs[left]];
                arr[nowIs[left]] = arr[nowIs[right]];
                arr[nowIs[right]] = p;
            }
        }
        arr[nowIs[startIndex]] = arr[nowIs[left]];
        arr[nowIs[left]] = pivot;
        return left;
    }
}
